package 排序算法;

import java.util.Arrays;

/**
 * 归并排序 ：这是数组版本的，如果要看链表版本见LC148：排序链表。但是中心思想都是差不多的
 */
public class MergerSort {
    //临时数组，要定义成全局变量，不然在merge方法中每次递归都会创建一个数组，解决问题时候很容易超时！！
    //我们一般都放入到不会递归的函数中去初始化
    int[] tmp;


    public static void main(String[] args) {
        int[] arr = {24, 5, 98, 28, 99, 56, 34, 2, 11};
        new MergerSort().MergeSort(arr);
        System.out.print(Arrays.toString(arr));
    }

    private void MergeSort(int[] arr) {
        tmp = new int[arr.length];
        Sort(arr, 0, arr.length - 1);
    }

    /**
     * 拆分
     *
     * @param a
     * @param left
     * @param right
     */
    private void Sort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;//从这里拆分
        //二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
        Sort(a, left, mid);
        Sort(a, mid + 1, right);
        merge(a, left, mid, right);
    }

    /**
     * 合并
     *
     * @param a
     * @param left
     * @param mid
     * @param right
     */
    private void merge(int[] a, int left, int mid, int right) {
        int k = left;//存放指针
        //下面这俩是检测指针
        int p1 = left;//左边的起始索引
        int p2 = mid + 1;//右边的起始索引
        // 逐个归并
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                tmp[k++] = a[p1++];
            } else {
                tmp[k++] = a[p2++];
            }
        }
        // //若左边序列还有剩余，则将其全部拷贝进tmp[]中：即将左边剩余的归并
        while (p1 <= mid) {
            tmp[k++] = a[p1++];
        }
        // 将右边剩余的归并
        while (p2 <= right) {
            tmp[k++] = a[p2++];
        }
        //将左右归并：存放入原数组
        for (int i = left; i <= right; i++) {
            a[i] = tmp[i];
        }
    }
}
